/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package gisgraph;

import edu.uci.ics.jung.algorithms.shortestpath.DijkstraShortestPath;
import gisgraph.components.*;
import java.util.ArrayList;
import edu.uci.ics.jung.graph.DirectedSparseGraph;
import edu.uci.ics.jung.graph.util.Pair;
import java.security.InvalidParameterException;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.List;
import java.util.Set;
import org.apache.commons.collections15.Transformer;
import org.jgrapht.traverse.TopologicalOrderIterator;
import org.jgrapht.experimental.dag.DirectedAcyclicGraph;
import org.jgrapht.experimental.dag.DirectedAcyclicGraph.CycleFoundException;

/**
 *
 * @author korek
 */
public class GISAlgorithm {
    ArrayList<StateVertex> stateList = new ArrayList();
    ArrayList<Node> nodeList = new ArrayList();
    ArrayList<Group> groupList = new ArrayList();
    GISGraphView console;
    
    // konstruktor
    public void GISAlgorithm() 
    {
        
    }
    
    public DirectedAcyclicGraph<StateVertex, JGraphEdge> start(DirectedAcyclicGraph<GISVertex, JGraphEdge>  graph, GISGraphView gView)
    {
        this.console = gView; // do drukowania informacji
        this.loadGraph(graph);
        this.createStates();        // tworzy z nodow stany
        //this.printStateList();
        this.createStatesGroups(graph);  // dzieli stany na grupy
        //this.printGroupList();
        
        try
        { 
            return createStateGraph(graph);         // tworzy krawedzie w grafie stanow
        }
        catch (Exception e)
        {
            System.out.println(e.getMessage());
            System.out.println(e.getStackTrace());
            
            return null;
        }
    }
    
    public void loadGraph(DirectedAcyclicGraph<GISVertex, JGraphEdge>  graph)
    {
        TopologicalOrderIterator<GISVertex, GISEdge> topological_iter = new TopologicalOrderIterator((org.jgrapht.DirectedGraph)graph);
        
        console.ConsoleWriteLine("Rozpoczynanie tworzenia grafu stanów...");
        console.ConsoleWriteLine("Kolejność topologiczna wierzchołków: ");
        
        String topologicalOrder = "";
        boolean isFirst = true;
        while(topological_iter.hasNext())
        {
            GISVertex v = topological_iter.next();
            
            //System.out.println(v.toString());
            this.nodeList.add(new Node(v.toString()));
            
            if (!isFirst) 
                topologicalOrder += ", ";
            
            topologicalOrder += v.toString();
            
            isFirst = false;
        }
        
        console.ConsoleWriteLine(topologicalOrder);
    }
    
    public void printStateList()
    {
        return;
        /*System.out.println("stany:");
        for(int i=0;i<stateList.size();++i)
            System.out.println(stateList.get(i).getName());*/
    }
    
    public void printGroupList()
    {
        return;
        /*System.out.println("grupy:");
        for(int i=0;i<groupList.size();++i)
        {
            System.out.println("grupa G"+groupList.get(i).getName()+", order= " + groupList.get(i).getOrder() + ", zawartosc:");
            for(int j = 0; j < groupList.get(i).getStatesInGroup().size(); ++j)
            {
                System.out.println(groupList.get(i).getStatesInGroup().get(j).getName());
            }
        }*/
    }
        
    public void createStatesGroups(DirectedAcyclicGraph<GISVertex, JGraphEdge>  graph)
    {
        this.createGroups(graph);
        TopologicalOrderIterator<GISVertex, JGraphEdge> tmp_iter = new TopologicalOrderIterator((org.jgrapht.DirectedGraph)graph);
        
        String vi, tmp_group = "";
        String[] states;
        
        for(int i = 0; i < stateList.size(); ++i)
        {
            states = stateList.get(i).getName().split(",");
            
            while(tmp_iter.hasNext())
            {
                vi = Integer.toString(tmp_iter.next().getId());
                //System.out.println("vi:"+vi+",s1:"+states[0]+",s2:"+states[1]);
                if(in_array(states, vi))
                {
                    //System.out.println("w stanie "+states[0]+","+states[1]+" jest "+vi);
                    tmp_group = vi;
                }
            }
            //System.out.println("stan: "+stateList.get(i).getName()+" do grupy G"+tmp_group);
            for(int j = 0; j < groupList.size(); ++j)
            {
                if(groupList.get(j).getName().equals(tmp_group))
                {
                    groupList.get(j).addState(stateList.get(i));
                    stateList.get(i).setGroup(groupList.get(j));
                }
            }           
            tmp_iter = new TopologicalOrderIterator((org.jgrapht.DirectedGraph)graph);
        }
    }
    
    private boolean in_array(String[] ar, String pattern)
    {
        if(ar[0].equals(pattern) || ar[1].equals(pattern) || ar[2].equals(pattern))
            return true;
        else
            return false;
    }
    
    private void createGroups(DirectedAcyclicGraph<GISVertex, JGraphEdge>  graph)
    {
        TopologicalOrderIterator<GISVertex, JGraphEdge> topological_iter = new TopologicalOrderIterator((org.jgrapht.DirectedGraph)graph);

        int topological_order = 0;
        while(topological_iter.hasNext())
        {   
            ++topological_order;
            this.groupList.add(new Group(topological_iter.next().toString(), topological_order));
        }
    }
        
    public DirectedAcyclicGraph<StateVertex, JGraphEdge> createStateGraph(DirectedAcyclicGraph<GISVertex, JGraphEdge>  graph) throws CycleFoundException
    {
        DirectedAcyclicGraph<StateVertex, JGraphEdge> stateGraph = new DirectedAcyclicGraph<StateVertex, JGraphEdge>(JGraphEdge.class);
        
        for(int i = 0; i < stateList.size(); ++i)
        {
            stateGraph.addVertex(stateList.get(i));
        }
        Set<StateVertex> vertices = stateGraph.vertexSet(); // stanow
        Set<JGraphEdge> edges = graph.edgeSet(); // pierwotnego!
        //ArrayList<GISVertex> graphVerticesPart = new ArrayList<GISVertex>(); // pierwotnego!
        
        Hashtable<Integer, GISVertex> graphVertices = new Hashtable<Integer, GISVertex>();
        Hashtable<Integer, StateVertex> stateVertices = new Hashtable<Integer, StateVertex>();
        Hashtable<Integer, Group> groups = new Hashtable<Integer, Group>();
//        for(StateVertex v : stateGraph.vertexSet())
//        {
//            graphVertices.put(v.ge, v);
//        }
        for(GISVertex v : graph.vertexSet())
        {
            graphVertices.put(v.getId(), v);
        }
        for(Group g : this.groupList)
        {
            groups.put(Integer.parseInt(g.getName()), g);
        }
        
        Iterator<StateVertex> iter1 = vertices.iterator();
        while(iter1.hasNext())
        {
            StateVertex first = iter1.next();
            Iterator<StateVertex> iter2 = vertices.iterator();
            while(iter2.hasNext())
            {
                StateVertex second = iter2.next();
                if(first.equals(second)) // nie sprawdzam samego z sobą
                    continue;
                //System.out.println("sprawdzam "+first.getName()+" -> "+second.getName());          
                if(first.getGroup().getOrder() < second.getGroup().getOrder()) // warunek j < i
                {
                    // warunek j < i spełniony :) yeah!
                    
                    TopologicalOrderIterator<GISVertex, JGraphEdge> topological_iter = new TopologicalOrderIterator((org.jgrapht.DirectedGraph)graph);
                    ArrayList<GISVertex> graphVerticesPart = new ArrayList<GISVertex>();
                    while(topological_iter.hasNext())
                    {
                        GISVertex tmpV = topological_iter.next();
                        if(groups.get(tmpV.getId()).getOrder() < second.getGroup().getOrder())
                            graphVerticesPart.add(tmpV); // tu sa l-ki, mniejsze od i
                    }
                    boolean Ml_mniejszerowne_Mi = true;
                    for(GISVertex g : graphVerticesPart)
                    {
                        if(first.countNodes(g.getId()) >= second.countNodes(g.getId())) // czy |Ml`| >= |Ml| dla kazdego
                        {}
                        else{
                            Ml_mniejszerowne_Mi = false;
                            break;
                        }
                    }                    
                    // sprawdzamy czy gdzies cos nie pykło
                    if(!Ml_mniejszerowne_Mi)
                        continue;
                    // jesli jest ok idziemy dalej
                    
                    // bedziemy sprawdzac czy wierzcholki sa ze soba w relacji pierwszenstwa (first poprzednikiem second)
                    
                    //sprawdzimy czy istnieje krawedz w pierwotnym grafie
                    boolean are_all_vertices = true;
                    boolean enough_capacity = true;
                    int weight = 0;
                    Hashtable<JGraphEdge, Integer> reliable = new Hashtable<JGraphEdge, Integer>();
                    for(GISVertex g : graphVerticesPart) 
                    {
                        if(first.countNodes(g.getId()) > second.countNodes(g.getId()))
                        {
                            if(graph.containsEdge(graphVertices.get(g.getId()), graphVertices.get(Integer.parseInt(second.getGroup().getName()))))
                            {
                                int cost;
                                cost = first.countNodes(g.getId()) - second.countNodes(g.getId());
                                if(!graph.getEdge(graphVertices.get(g.getId()), graphVertices.get(Integer.parseInt(second.getGroup().getName()))).getIsReliable() && cost > 1)
                                {
                                    enough_capacity = false;
                                    break;
                                }else{
                                    //System.out.println("jest krawedz");
                                    JGraphEdge tmpEdge = graph.getEdge(graphVertices.get(g.getId()), graphVertices.get(Integer.parseInt(second.getGroup().getName())));
                                    if(tmpEdge.getIsReliable())
                                    {
                                        if(!reliable.containsKey(tmpEdge))
                                        {
                                            reliable.put(tmpEdge, tmpEdge.getWeight());
                                            weight += tmpEdge.getWeight();
                                        }else
                                        {
                                           // nic
                                        }
                                    }else
                                    {
                                        //System.out.println("dodaje do wagi: "+tmpEdge.getWeight());
                                        weight += tmpEdge.getWeight();
                                    }
                                }                        
                            }
                            else 
                            {
                                are_all_vertices = false;
                                break;
                            }
                        }
                    }
                    // sprawdzamy czy istnieja wszystkie krawedzie ktore powinny w pierwotnym grafie
                    if(!are_all_vertices || !enough_capacity)
                    {
                        weight = 0;
                        continue;
                    }
                    // jesli jest ok to jedziemy dalej
                    
                    // po tych wszystkich sprawdzeniach, jesli ciagle tu jestesmy to znaczy ze jest OK i krawedz miedzy first i second w grafie stanow istnieje
                    // zatem zrobmy ja
                    JGraphEdge edge = new JGraphEdge(false);
                    edge.setWeight(weight);
                    stateGraph.addDagEdge(first, second, edge);
                    
                    String edgeInfo = "dodano krawedz " + first.getName() + " -> " + second.getName() + " z wagą " + weight;
                    
                    //System.out.println(edgeInfo);
                    
                    console.ConsoleWriteLine(edgeInfo);
                    
                    weight = 0;
                }
            }            
            
        }
        
        return stateGraph;
    }
    
    /**
     * tworzy stany, ktore sa permutacjami z powtorzeniami wszystkich wierzchołkow
     */
    public void createStates()
    {
        int z = 2; // stany zlozone z "z" wierzcholkow
        for(int i = 0, j = 0, k = 0; i < nodeList.size()-1; ++k)
        {
            if(k == nodeList.size())
            {
                ++j;
                k = j;
                if(j == nodeList.size())
                {
                    ++i;
                    k = j = i;
                }
            }
            stateList.add(new StateVertex(nodeList.get(i).getName() + "," + nodeList.get(j).getName() + "," + nodeList.get(k).getName(), Integer.parseInt(nodeList.get(i).getName()), Integer.parseInt(nodeList.get(j).getName()), Integer.parseInt(nodeList.get(k).getName())));
        }        
    }
    
    public static List<GISEdge> findPaths(DirectedSparseGraph<StateVertex, GISEdge> jungGraph, GISVertex startVertex, GISVertex endVertex, GISGraphView console)
    {
        int pathNr = 1;
        
        StateVertex v1 = null;
        StateVertex v2 = null;

        for (StateVertex v : jungGraph.getVertices())
        {
            int startId = startVertex.getId();
            int endId = endVertex.getId();
            
            if (v.getId1() == startId && v.getId2() == startId && v.getId3() == startId)
            {
                v1 = v;
            }
            else if (v.getId1() == endId && v.getId2() == endId && v.getId3() == endId)
            {
                v2 = v;
            }
        }
        
        if (v1 == null || v2 == null)
        {
            throw new InvalidParameterException("Nie podano wierzchołka początkowego lub końcowego");
        }
        
        Transformer<GISEdge, Number> edgeTransformer = new Transformer<GISEdge, Number>() {
            @Override
            public Number transform(GISEdge i) {
                return i.getWeight();
            }
        };

        DijkstraShortestPath<StateVertex, GISEdge> dijkstra = 
                new DijkstraShortestPath<StateVertex, GISEdge>(jungGraph, edgeTransformer);
        
        
        List<GISEdge> path = dijkstra.getPath(v1, v2);
        
        
        String statePath = "Najkrótsza ścieżka w grafie stanów: ";
        int weight = 0;
        boolean first = true;
        
        for (GISEdge e : path)
        {
            weight += e.getWeight();
            
            Pair<StateVertex> eps = jungGraph.getEndpoints(e);
            
            if (first) 
            {
                statePath += ", (" + eps.getFirst().toString() + ")";
                first = false;
            }
            
            statePath += ", (" + eps.getSecond().toString() + ")";
        }
        
        statePath += " o wadze: " + ((Integer)weight).toString();
        console.ConsoleWriteLine(statePath);

        return path;
    }
}

